package dynamicProgramming.MatrixPathProblem;

/**
 * @author zxc
 * @date 2023/01/24 15:36
 **/

import java.util.Arrays;

/**
 * 题目 ：路径的数目
 * 题目详述 ：
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * 提示：
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 109
 */
public class UniquePaths04 {
    /**
     * 思路 ：
     * 假设f(i,j)为机器人当前所在位置可能的路径数目;
     * 1.考虑特殊情况
     * （1）当i == 0时，同时又由于机器人只能够向右/下走，所以f(0,j) == 1（只可能是机器人向右走，直至走到坐标(0,j)为止）
     * （2）当j == 0时，同时又由于机器人只能够向右/下走，所以f(i,0) == 1（只可能时机器人向下走，直至走到坐标(i,0)为止）
     * 2.考虑一般情况
     * 当i > 0 && j > 0时，则f(i,j) = f(i-1,j) + f(i,j-1);
     * ===> 可以大致理解为，要求去f(i,j),只需要在f(i-1,j)向右走一步 || f(i,j-1)向下走一步;
     * @param m
     * @param n
     * @return
     */
    // 迭代代码实现 : 一维数组
    public int uniquePaths(int m, int n) {
        // 迭代实现 ：即，f(i,j)为(i + 1) * (j + 1)大小网格的所以可能路线数量;
        int [] temp = new int[n];

        // 调用Arrays.fill工具类，将某个指定长度n的数组temp中所有元素赋予初始值;
        Arrays.fill(temp , 1);

        // 初始化temp[0][0];
        // 同时，一维数组temp的首个元素temp[0]都为1;所以不需要对其进行改变
//        temp[0] = 1;
//        for(int j = 1;j < n;j++){
//            temp[j] = 1;
//        }

        // for循环 ：遍历所有可能到达的坐标坐标;
        // 普通情况 ：temp[i][j] = temp[i-1][j] + temp[i][j-1];
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                // 在遍历i + 1时，temp[j]和temp[j-1]所保存的是，遍历i时的temp[j] && temp[j-1];
                temp[j] = temp[j] + temp[j - 1];
            }
        }
        return temp[n - 1];
    }
}
